package com.cet.programmercarl.algorithmperformancanalysis.二叉树.二叉树的遍历;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @program: algorithm
 * @description: 二叉树前序遍历
 * @author: 陈恩涛
 * @create: 2022-07-13 21:33
 **/
public class LC144 {

    public static void main(String[] args) {

    }

    /**
     * 递归遍历
     * @param root 根节点
     * @return 结果
     */
    public static List<Integer> preorderTraversal(TreeNode root) {
        final List<Integer> list = new ArrayList<>();
        preorderTraversal(root, list);
        return list;
    }

    private static void preorderTraversal(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        list.add(node.val);
        preorderTraversal(node.left, list);
        preorderTraversal(node.right, list);
    }

    /**
     * 迭代遍历
     * @param root 根节点
     * @return 结果
     */
    public List<Integer> preorderTraversal2(TreeNode root) {
        final List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        final Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            final TreeNode node = stack.pop();
            result.add(node.val);
            // 中左右遍历顺序
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }

    /**
     * 标记节点法（二次访问标记），统一格式
     * @param root 二叉树根节点
     * @return 结果
     */
    public List<Integer> preorderTraversal3(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root != null) {
            st.push(root);
        }
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop(); // 将该节点弹出，避免重复操作，下面再将右中左节点添加到栈中
                if (node.right!=null) {
                    st.push(node.right);  // 添加右节点（空节点不入栈）
                }
                if (node.left!=null) {
                    st.push(node.left);    // 添加左节点（空节点不入栈）
                }
                st.push(node);                          // 添加中节点
                st.push(null); // 中节点访问过，但是还没有处理，加入空节点做为标记。

            } else { // 只有遇到空节点的时候，才将下一个节点放进结果集
                st.pop();           // 将空节点弹出
                node = st.peek();    // 重新取出栈中元素
                st.pop();
                result.add(node.val); // 加入到结果集
            }
        }
        return result;
    }

}


